import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * 
 * @author Eric Beaudry
 */
public class GenPolitique2 {

	private ActionType[][] computePlan(Plateau plateau) throws FileNotFoundException, IOException {

		long startTime = System.currentTimeMillis();

		GenPolitique1 pol1Generator = new GenPolitique1();

		Double[] pol1ValueMatrix = new Double[plateau.nbCases];
		ActionType[] pol1Plan = pol1Generator.computePlan(plateau, pol1ValueMatrix);

		ActionType[][] planMatrix = new ActionType[plateau.nbCases][plateau.nbCases];
		double[][] rewardMatrix = new double[plateau.nbCases][plateau.nbCases];

		for (int i = 0; i < plateau.nbCases; ++i) {
			for (int j = 0; j < plateau.nbCases; ++j) {
				planMatrix[j][i] = pol1Plan[j];
				rewardMatrix[i][j] = (double) (plateau.getNextCase(i, 0) - plateau.getNextCase(j, 0));
			}
		}

		for (int i = plateau.nbCases - 13; i < plateau.nbCases - 1; ++i) {
			for (int j = plateau.nbCases - 12; j < plateau.nbCases - 1; ++j) {
				if (rewardMatrix[i][j] < 0) {
					if (isInTwoDiceRange(plateau, i)) {
						planMatrix[i][j] = ActionType.DeuxDes;
					} else if (isInOneDiceRange(plateau, i)) {
						planMatrix[i][j] = ActionType.UnDe;
					}
				}
			}
		}

		int cpt = 0;
		while (System.currentTimeMillis() < startTime + 9850) {
			// while (cpt < 2) {

			for (int i = plateau.nbCases - 2; i > 0; --i) {
				// for (int i = 0; i < plateau.nbCases - 1; ++i) {
				for (int j = plateau.nbCases - 2; j >= 0; --j) {
					// for (int j = 0; j < plateau.nbCases - 1; ++j) {
					if (!(isInDesperateRange(plateau, plateau.getNextCase(i, 0)) && isInDesperateRange(plateau, plateau.getNextCase(j, 0)))) {
						if (Math.abs(plateau.getNextCase(i, 0) - plateau.getNextCase(j, 0)) >= (plateau.nbCases * 0.4)) {
							FindNextBestAction(i, j, plateau, pol1Plan, planMatrix, rewardMatrix);
						}
					}
				}

			}

			cpt++;
		}

		return planMatrix;
	}

	private boolean isInDesperateRange(Plateau plateau, int position) {
		return isInOneDiceRange(plateau, position) || isInTwoDiceRange(plateau, position);
	}

	private boolean isInOneDiceRange(Plateau plateau, int i) {
		return i >= plateau.nbCases - 7 && i <= plateau.nbCases - 2;
	}

	private boolean isInTwoDiceRange(Plateau plateau, int i) {
		return i >= plateau.nbCases - 13 && i <= plateau.nbCases - 8;
	}

	private double getReward(Plateau plateau, int currentPosition) {
		if (currentPosition == plateau.nbCases - 1) {
			return 5d;
		}

		return 0d;
	}

	private double getRewardUneCase(Plateau plateau, int currentPosition) {

		double reward = getReward(plateau, plateau.getNextCase(currentPosition, 1));

		return reward;
	}

	private double getRewardUnDe(Plateau plateau, int currentPosition) {

		double reward = 0d;

		for (int i = 1; i < 7; ++i) {
			reward += getReward(plateau, plateau.getNextCase(currentPosition, i));
		}
		if (reward > 1000) {
			reward = 1000d;
		}
		return reward;
	}

	private double getRewardDeuxDe(Plateau plateau, int currentPosition) {

		double reward = 0d;

		for (int i = 2; i < 13; ++i) {
			reward += getReward(plateau, plateau.getNextCase(currentPosition, i));
		}
		if (reward > 1000) {
			reward = 1000d;
		}
		return reward;
	}

	/**
	 * @param currentPosition
	 * @param currentEnnemyPosition
	 * @param p
	 * @param pol1Plan
	 * @param planMatrix
	 * @param rewardMatrix
	 */
	private void FindNextBestAction(int currentPosition, int currentEnnemyPosition, Plateau p, ActionType[] pol1Plan, ActionType[][] planMatrix, double[][] rewardMatrix) {
		ActionType nextEnnemyMove = pol1Plan[currentEnnemyPosition];
		double oneStepValue = -1000.0;
		double oneDiceValue = -1000.0;
		double twoDiceValue = -1000.0;

		if (nextEnnemyMove == ActionType.UneSeuleCase) {
			oneStepValue = Calculate_Me1_Ennemy1(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUneCase(p, currentPosition);
			oneDiceValue = Calculate_MeD_Ennemy1(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUnDe(p, currentPosition);
			twoDiceValue = Calculate_MeDD_Ennemy1(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardDeuxDe(p, currentPosition);
		} else if (nextEnnemyMove == ActionType.UnDe) {
			oneStepValue = Calculate_Me1_EnnemyD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUneCase(p, currentPosition);
			oneDiceValue = Calculate_MeD_EnnemyD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUnDe(p, currentPosition);
			twoDiceValue = Calculate_MeDD_EnnemyD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardDeuxDe(p, currentPosition);
		} else {
			oneStepValue = Calculate_Me1_EnnemyDD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUneCase(p, currentPosition);
			oneDiceValue = Calculate_MeD_EnnemyDD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardUnDe(p, currentPosition);
			twoDiceValue = Calculate_MeDD_EnnemyDD(currentPosition, currentEnnemyPosition, p, rewardMatrix) + getRewardDeuxDe(p, currentPosition);
		}

		if (oneStepValue > oneDiceValue && oneStepValue > twoDiceValue) {
			planMatrix[currentPosition][currentEnnemyPosition] = ActionType.UneSeuleCase;
			rewardMatrix[currentPosition][currentEnnemyPosition] = oneStepValue;
		} else if (oneDiceValue >= oneStepValue && oneDiceValue > twoDiceValue) {

			planMatrix[currentPosition][currentEnnemyPosition] = ActionType.UnDe;

			rewardMatrix[currentPosition][currentEnnemyPosition] = oneDiceValue;
		} else {
			planMatrix[currentPosition][currentEnnemyPosition] = ActionType.DeuxDes;
			rewardMatrix[currentPosition][currentEnnemyPosition] = twoDiceValue;
		}

	}

	private double Calculate_MeDD_EnnemyDD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int foe_d1 = 1; foe_d1 < 7; ++foe_d1) {
			for (int foe_d2 = 1; foe_d2 < 7; ++foe_d2) {
				for (int my_d1 = 1; my_d1 < 7; ++my_d1) {
					for (int my_d2 = 1; my_d2 < 7; ++my_d2) {
						value += rewardMatrix[p.getNextCase(currentPosition, my_d1 + my_d2)][p.getNextCase(currentEnnemyPosition, foe_d1 + foe_d2)] / 1296d;
					}
				}
			}
		}
		return value;
	}

	private double Calculate_MeD_EnnemyDD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int foe_d1 = 1; foe_d1 < 7; ++foe_d1) {
			for (int foe_d2 = 1; foe_d2 < 7; ++foe_d2) {
				for (int my_d1 = 1; my_d1 < 7; ++my_d1) {
					value += rewardMatrix[p.getNextCase(currentPosition, my_d1)][p.getNextCase(currentEnnemyPosition, foe_d1 + foe_d2)] / 216d;
				}
			}
		}
		return value;
	}

	private double Calculate_Me1_EnnemyDD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int d1 = 1; d1 < 7; ++d1) {
			for (int d2 = 1; d2 < 7; ++d2) {
				value += rewardMatrix[p.getNextCase(currentPosition, 1)][p.getNextCase(currentEnnemyPosition, d1 + d2)] / 36d;
			}
		}
		return value;
	}

	private double Calculate_Me1_EnnemyD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {

		double value = 0.0;
		for (int i = 1; i < 7; ++i) {
			value += rewardMatrix[p.getNextCase(currentPosition, 1)][p.getNextCase(currentEnnemyPosition, i)] / 6d;
		}
		return value;
	}

	private double Calculate_MeD_EnnemyD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int d1 = 1; d1 < 7; ++d1) {
			for (int d2 = 1; d2 < 7; ++d2) {
				value += rewardMatrix[p.getNextCase(currentPosition, d1)][p.getNextCase(currentEnnemyPosition, d2)] / 36d;
			}
		}
		return value;
	}

	private double Calculate_MeDD_EnnemyD(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int my_d1 = 1; my_d1 < 7; ++my_d1) {
			for (int my_d2 = 1; my_d2 < 7; ++my_d2) {
				for (int foe_d1 = 1; foe_d1 < 7; ++foe_d1) {
					value += rewardMatrix[p.getNextCase(currentPosition, my_d1 + my_d2)][p.getNextCase(currentEnnemyPosition, foe_d1)] / 216d;
				}
			}
		}
		return value;
	}

	private double Calculate_MeDD_Ennemy1(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {
		double value = 0.0;
		for (int d1 = 1; d1 < 7; ++d1) {
			for (int d2 = 1; d2 < 7; ++d2) {
				value += rewardMatrix[p.getNextCase(currentPosition, d1 + d2)][p.getNextCase(currentEnnemyPosition, 1)] / 36d;
			}
		}
		return value;
	}

	private double Calculate_MeD_Ennemy1(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {

		double value = 0.0;
		for (int i = 1; i < 7; ++i) {
			value += rewardMatrix[p.getNextCase(currentPosition, i)][p.getNextCase(currentEnnemyPosition, 1)] / 6d;
		}
		return value;
	}

	private double Calculate_Me1_Ennemy1(int currentPosition, int currentEnnemyPosition, Plateau p, double[][] rewardMatrix) {

		return rewardMatrix[p.getNextCase(currentPosition, 1)][p.getNextCase(currentEnnemyPosition, 1)];
	}

	static PolitiqueAvancee generate(Plateau plateau, ActionType[][] plan) {
		PolitiqueAvancee pol = new PolitiqueAvancee(plateau.nbCases);

		for (int i = 0; i < plateau.nbCases; i++)
			for (int j = 0; j < plateau.nbCases; j++)
				pol.actions[i][j] = plan[i][j];

		return pol;
	}

	public static void main(String args[]) throws Exception {
		Plateau plateau = Plateau.load(new InputStreamReader(System.in));

		// Plateau plateau = Plateau.load(new FileReader(new
		// File("plateau1.txt")));

		GenPolitique2 generator = new GenPolitique2();
		ActionType[][] plan = generator.computePlan(plateau);
		PolitiqueAvancee pol = generate(plateau, plan);

		OutputStreamWriter out = new OutputStreamWriter(System.out);
		PolitiqueAvancee.save(pol, out);
		out.close();
	}

}
